package beike.tree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author youli
 *定义二叉树，先序、中序、后序、分层遍历
 *二叉树初始化：构造一颗完全二叉树
 *输入格式：
 *1,2,3,4,5,6,7
 *树中节点值均大于0，数组元素为0，则表示树中对应节点为空
 *录入数据时，请按照满二叉数形式录入，空子树使用null表示
 *输出格式：
 * 2023年11月6日
 */
public class TreeDemo {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		
		String[] arr = line.split(",");
		
		int[] nums = new int[arr.length];
		
		for(int i=0;i<arr.length;i++) {
			if(arr[i].equals("null")) {
				nums[i] = 0;
			}else {
				nums[i] = Integer.valueOf(arr[i]);
			}
		}		
		TreeNode root = initTree(nums);
		System.out.println("----------先序----------");
		preOrder(root);
		System.out.println();
		System.out.println("----------中序----------");
		inOrder(root);
		System.out.println();
		System.out.println("----------后序----------");
		postOrder(root);
		System.out.println();
		System.out.println("----------层序----------");
		levelOrder(root);
	}
	
	
	//当前元素为i，其父节点为(i-1)/2,左孩子节点为2*i+1，右孩子节点为2*i+2
	public static TreeNode initTree(int[] nums) {
		TreeNode[] nodes = new TreeNode[nums.length];
		for(int i=0;i<nums.length;i++) {
			if(nums[i] == 0) {
				nodes[i] = null;
			}else {
				nodes[i] = new TreeNode(nums[i]);
			}			
		}
		for(int i=0;i<nums.length;i++) {
			int leftIndex = 2*i+1;
			int rightIndex = 2*i+2;
			if(nodes[i]!=null && leftIndex<nums.length) {
				nodes[i].left = nodes[leftIndex];
			}
			if(nodes[i]!=null && leftIndex<nums.length) {
				nodes[i].right = nodes[rightIndex];
			}
		}		
		return nodes[0];
	}
	
	public static void preOrder(TreeNode root) {
		if(root == null) {
			return;
		}
		System.out.print(root.val+" ");
		preOrder(root.left);
		preOrder(root.right);
	}
	
	public static void inOrder(TreeNode root) {
		if(root == null) {
			return;
		}
		inOrder(root.left);
		System.out.print(root.val+" ");
		inOrder(root.right);		
	}
	
	public static void postOrder(TreeNode root) {
		if(root == null) {
			return;
		}
		postOrder(root.left);
		postOrder(root.right);	
		System.out.print(root.val+" ");
	}
	
	
	public static void levelOrder(TreeNode root) {
		if(root == null) {
			return;
		}
		Queue<TreeNode> q = new LinkedList<>();
		q.offer(root);
		while(q.size() > 0) {
			TreeNode node = q.poll();
			System.out.print(node.val + " ");
			if(node.left != null) {
				q.offer(node.left);
			}
			if(node.right != null) {
				q.offer(node.right);
			}
		}
	}
	/**
	    1、如果一个节点有右节点没有左节点肯定不是完全二叉树
	    2、如果已经出现一个节点没有右节点，接着又出现了一个节点有子节点那肯定也不是
	 */
	public static boolean isCompleteTree(TreeNode root) {
		Queue<TreeNode> q = new LinkedList<>();
		//标志位，判断是否已经出现一个节点没有有节点
		boolean flag = false;
		q.offer(root);
		while(!q.isEmpty()) {
			TreeNode node = q.poll();
			//条件1
			if(node.right != null && node.left == null) {
				return false;
			}
			//条件2
			if(flag && (node.left != null || node.right != null)) {
				return false;
			}
			if(node.left != null) {
				q.offer(node.left);
			}
			if(node.right != null) {
				q.offer(node.right);
			}else {
				flag = true;
			}
		}
		return true;
	}

}


















